﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;


namespace ThuatToanThongMinh
{
    /**-----------------------------------------------------------
    * Program/Project : madituan
    * Nguoi viet : Tran Thanh Son
    * Email : soncntt251@gmail.com
    * Mo ta: Day la phan chinh cua chuong trinh thuc thi va duyet ma
    ---------------------------------------------------------*/
    struct Co
    {
        public int x;
        public int y;
        //public int trangthai;
        public int trongso;
    }
    class madituan
    {
        private int Kthuoc;
        private int X;
        private int Y;
        private int[,] banco;
        private Co[] _dd;
        private Co[] Vitri;
        //Cac phuong thuc

        /**-----------------------------------------------------------
        * Mo ta: Khoi gan cac thong tin ban dau duoc cho tu bai toan
        * Ten phuong thuc: Set
        * Tham so:co cac tham so hinh thuc la _kt, _x, _y là kich thuoc, toa do X va toa do Y cua con co vi tri xuat phat
        * Gia tri tra ve: void, khong co gia tri tra ve
        ---------------------------------------------------------*/
        public void Set(int _kt, int _x, int _y)
        {
            Kthuoc = _kt;
            X = _x;
            Y = _y;
        }
        public Co[] GetVT()
        {
            return Vitri;
        }
        /**-----------------------------------------------------------
        * Mo ta: Khoi tao gia tri ban dau can thiet cho bai toan nhu ban  co nhi phan, khoi gan cac kha nang
        * Ten phuong thuc:  KhoiTao
        * Tham so: khong co
        * Gia tri tra ve: khong co gia tri tra ve
        ---------------------------------------------------------*/
        public void KhoiTao()
        {
            int i;
            banco = new int[Kthuoc, Kthuoc];
            // dua gia tri ban co ve 0
            for (i = 0; i < Kthuoc; i++)
                for (int j = 0; j < Kthuoc; j++)
                {
                    banco[i, j] = new int();
                    banco[i, j] = 0;
                }
            banco[X, Y] = 1;

            //khoi tao mang luu vi tri con co
            Vitri = new Co[Kthuoc * Kthuoc];
            for (i = 0; i < Kthuoc * Kthuoc; i++)
            {
                Vitri[i] = new Co();
                Vitri[i].x = Vitri[i].y = 0;
            }
            Vitri[0].x = X;
            Vitri[0].y = Y;

            //khoi tao 8 con co co the di tiep cua quan ma

            _dd = new Co[8];
            for (i = 0; i < 8; i++)
            {
                _dd[i] = new Co();
                //dd[i].trangthai = 0;
                _dd[i].trongso = 0;
            }

            // Cac buoc di ma ngua co the di qua
            //1
            _dd[0].x = 2;
            _dd[0].y = -1;
            //2
            _dd[1].x = 1;
            _dd[1].y = -2;
            //3
            _dd[2].x = -1;
            _dd[2].y = -2;
            //4
            _dd[3].x = -2;
            _dd[3].y = -1;
            //5
            _dd[4].x = -2;
            _dd[4].y = 1;
            //6
            _dd[5].x = -1;
            _dd[5].y = 2;
            //7
            _dd[6].x = 1;
            _dd[6].y = 2;
            //8
            _dd[7].x = 2;
            _dd[7].y = 1;
        }
        /**-----------------------------------------------------------
        * Mo ta: Tinh trong so cho cac kha nang de sau do dua vao va sap xep
        * Ten phuong thuc: TinhTrongSo
        * Tham so: T_Co la bien tham so Co().
        * Gia tri tra ve: Gia tri tra ve la trong so cua kha nang
        ---------------------------------------------------------*/
        private int TinhTrongSo(Co T_Co)
        {
            int count = 0;
            int u, v;
            for (int i = 0; i < 8; i++)
            {
                u = T_Co.x + _dd[i].x;
                v = T_Co.y + _dd[i].y;
                if ((0 <= u) && (u < Kthuoc) && (0 <= v) && (v < Kthuoc) && (banco[u, v] == 0))
                {
                    count++;
                }
            }
            return count;
        }
        //Ham hoan vi hai con co
        private void Swap(ref Co x, ref Co y)
        {
            Co temp = new Co();
            temp = x;
            x = y;
            y = temp;
        }
        /**-----------------------------------------------------------
        * Mo ta: Sap xep cac kha nang dua vao trongso cua kha nang
        * Ten phuong thuc: SX_Min
        * Tham so: Mang Co[]
        * Gia tri tra ve: Khong co gia tri tra ve
        ---------------------------------------------------------*/
       
        private void SX_Min(Co[] T_Co)
        {
            int min;
            for (int i = 0; i < 7; i++)
            {
                min = i;
                for (int j = i + 1; j < 8; j++)
                    if (T_Co[j].trongso < T_Co[min].trongso)
                        min = j;
                Swap(ref T_Co[min], ref T_Co[i]);
            }

        }
        /**-----------------------------------------------------------
        * Mo ta: Day la ham chinh xu li chuong trinh, xu li qua trinh duyet quan ma
        * Ten phuong thuc: XuLy
        * Tham so: Tham so bao gom toa do cua quan co( _x, _y), va so thu tu cua con co do(_i)
        * Gia tri tra ve: khong co gia tri tra ve
        ---------------------------------------------------------*/
        public void Xuly(ref int _i, int _x, int _y)
        {
            int k = 0;
            int t1;
            Co[] Khanang = new Co[8];
            for (int i = 0; i < 8; i++)
            {
                Khanang[i] = new Co();
                Khanang[i].x = _dd[i].x + _x;
                Khanang[i].y = _dd[i].y + _y;
                Khanang[i].trongso = 0;
                //_dd[i].trangthai = 0;
                Khanang[i].trongso = TinhTrongSo(Khanang[i]);
            }
            SX_Min(Khanang);// sap xep kha nang
            do
            {
                t1 = 0;
                if (Khanang[k].x >= 0 && Khanang[k].y >= 0 && Khanang[k].x < Kthuoc && Khanang[k].y < Kthuoc && banco[Khanang[k].x, Khanang[k].y] == 0)
                {
                    if (_i < Kthuoc * Kthuoc)
                    {
                        banco[Khanang[k].x, Khanang[k].y] = _i;
                        Vitri[_i].x = Khanang[k].x;
                        Vitri[_i].y = Khanang[k].y;
                        //_dd[k].trangthai = 1;
                        _i++;
                        Xuly(ref _i, Khanang[k].x, Khanang[k].y);
                    }
                    else
                        t1 = 1;
                }
                k++;
            } while (t1 == 0 && k < 8);
        }
    }
}
